import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

// 定义图的节点类
class Node {
    public int val;
    public List<Node> neighbors;

    public Node() {
        val = 0;
        neighbors = new ArrayList<>();
    }

    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<>();
    }

    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}

public class Solution {
    public Node cloneGraph(Node node) {
        Map<Node, Node> lookup = new HashMap<>();
        return dfs(node, lookup);
    }

    private Node dfs(Node node, Map<Node, Node> lookup) {
        if (node == null) return null;
        if (lookup.containsKey(node)) return lookup.get(node);
        Node clone = new Node(node.val, new ArrayList<>());
        lookup.put(node, clone);
        for (Node n : node.neighbors) clone.neighbors.add(dfs(n, lookup));
        return clone;
    }

    public static void main(String[] args) {
        // 创建一个简单的图
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);

        node1.neighbors.add(node2);
        node1.neighbors.add(node4);
        node2.neighbors.add(node1);
        node2.neighbors.add(node3);
        node3.neighbors.add(node2);
        node3.neighbors.add(node4);
        node4.neighbors.add(node1);
        node4.neighbors.add(node3);

        // 克隆图
        Solution solution = new Solution();
        Node clonedNode = solution.cloneGraph(node1);

        // 打印克隆图的节点值和邻居节点值
        printGraph(clonedNode);
    }

    // 辅助方法：打印图的节点值和邻居节点值
    private static void printGraph(Node node) {
        if (node == null) return;
        Map<Node, Boolean> visited = new HashMap<>();
        dfsPrint(node, visited);
    }

    private static void dfsPrint(Node node, Map<Node, Boolean> visited) {
        if (node == null || visited.containsKey(node)) return;
        visited.put(node, true);
        System.out.print("Node " + node.val + " neighbors: ");
        for (Node neighbor : node.neighbors) {
            System.out.print(neighbor.val + " ");
        }
        System.out.println();
        for (Node neighbor : node.neighbors) {
            dfsPrint(neighbor, visited);
        }
    }
}